#include <stdio.h>
#include "STACK.h"
#include "QUEUE.h"

typedef struct bt_node* link;

struct bt_node {
    char item;
    link l;
    link r;
};

void trav_pre(link h, void (*visit)(link));
void trav_in(link h, void (*visit)(link));
void trav_post(link h, void (*visit)(link));
void trav_level(link h, void (*visit)(link));
void visit(link node);


int main(int argc, char* argv[]) {
    struct bt_node root;
    struct bt_node dNode;
    struct bt_node hNode;
    struct bt_node bNode;
    struct bt_node fNode;
    struct bt_node aNode;
    struct bt_node cNode;
    struct bt_node gNode;





    root.item = 'E';
    root.l = &dNode;
    root.r = &hNode;

    dNode.item = 'D';
    dNode.l = &bNode;
    dNode.r = NULL;
    hNode.item = 'H';
    hNode.l = &fNode;
    hNode.r = NULL;

    bNode.item = 'B';
    bNode.l = &aNode;
    bNode.r = &cNode;
    fNode.item = 'F';
    fNode.l = NULL;
    fNode.r = &gNode;

    aNode.item = 'A';
    aNode.l = NULL;
    aNode.r = NULL;
    cNode.item = 'C';
    cNode.l = NULL;
    cNode.r = NULL;
    gNode.item = 'G';
    gNode.l = NULL;
    gNode.r = NULL;

    trav_pre(&root, visit);
    printf("\n");
    trav_in(&root, visit);
    printf("\n");
    trav_post(&root, visit);
    printf("\n");
    trav_level(&root, visit);
    printf("\n");
    return 0;
}

/**
 * Program 5.14 Recursive tree traversal
 * ---------------------------------------------------------------
 * This recursive function takes a link to a tree as an argument and 
 * calls the function visit with each of the nodes in the tree as argument.
 * As is, the function implements a preorder traversal; 
 * if we move the call to visit between the recursive calls, we have an inorder traversal;
 * and if we move the call to visit after the recursive calls, we have a postorder traversal.
 */
void trav_pre(link h, void (*visit)(link)){
    if (h == NULL) {
        return ;
    }
    STACKinit(16);
    STACKpush(h);
    while(!STACKempty()){
        h = STACKpop();
        (*visit)(h);
        if (h->r != NULL) {
            STACKpush(h->r);
        }
        if (h->l != NULL) {
            STACKpush(h->l);
        }
        
    }
}

void trav_in(link h, void (*visit)(link)){
    STACKinit(16);
    link curr = h;
    while(curr != NULL || !STACKempty()){
        while (curr != NULL) {
            STACKpush(curr);
            curr = curr->l;
        }
        curr = STACKpop();
        (*visit)(curr);
        curr = curr->r;
    }
}

void trav_post(link h, void (*visit)(link)){
    STACKinit(16);
    link curr = h;
    link last_visited_node = NULL;
    while(curr != NULL || !STACKempty()){
        while (curr != NULL) {
            STACKpush(curr);
            curr = curr->l;
        }
        link peek_node = STACKpeek();
        if (peek_node->r == NULL || peek_node->r == last_visited_node) {
            curr = STACKpop();
            (*visit)(curr);
            last_visited_node = curr;
            curr = NULL;
        }else {
            curr = peek_node->r;
        }
    }
}

void trav_level(link h, void (*visit)(link)){
    QUEUEinit(16);
    QUEUEput(h);
    while (!QUEUEempty()) {
        h = QUEUEget();
        (*visit)(h);
        if (h->l != NULL) {
            QUEUEput(h->l);
        }
        if (h->r != NULL) {
            QUEUEput(h->r);
        }
    }
}

void visit(link node){
    printf("%c ", node->item);
}